#leetcode题目739：每日温度
#难度：中等
#时间复杂度：O(n)
#空间复杂度：O(n)
#方法：栈,单调栈的应用，反向遍历

from typing import List
class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        """
        每日温度
        给定一个整数数组 temperatures，表示每天的温度，返回一个数组 answer，
        其中 answer[i] 是指在第 i 天之后，才会有更高的温度。
        如果气温在这之后都不会升高，请在该位置用 0 来代替。
        """
        # 使用list作为单调栈，存储索引
        stack = []
        n = len(temperatures)
        res = [0] * n
        
        # 从右到左遍历，也就是反向遍历
        for i in range(n - 1, -1, -1):
            # 维护单调栈：移除所有温度小于等于当前温度的索引
            while stack and temperatures[i] >= temperatures[stack[-1]]:
                stack.pop()
            
            # 计算结果
            res[i] = 0 if not stack else stack[-1] - i
            
            # 将当前索引压入栈
            stack.append(i)
        
        return res




#测试数据
temperatures = [73,74,75,71,69,72,76,73]
#预期输出：[1,1,4,2,1,1,0,0]
solution = Solution()
print(solution.dailyTemperatures(temperatures))


temperatures = [30,40,50,60]
#预期输出：[1,1,1,0]
solution = Solution()
print(solution.dailyTemperatures(temperatures))

temperatures = [30,60,90]
#预期输出：[1,1,0]
solution = Solution()
print(solution.dailyTemperatures(temperatures))
